/**
 * 剑指 Offer 44. 数字序列中某一位的数字
 * https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/
 */

/**
 * @param {number} n
 * @return {number}
 */
function findNthDigit(n) {
  if (n < 10) {
    return n;
  }
  // 计算下标对应的数的数值位数
  let digitCount = 1;
  let beginVal = 0;
  let begin = 0;
  let endVal = 10;
  let end = 10;
  while (n >= end) {
    digitCount += 1;
    beginVal = endVal;
    begin = end;
    endVal = 10 ** digitCount;
    end += ((endVal - beginVal) * digitCount);
  }
  // console.log(beginVal, endVal);
  // console.log(begin, end);
  // 从数值高位开始遍历，逐渐缩小区间
  for (let i = 0; i < digitCount; i += 1) {
    const splitVal = 10 ** (digitCount - i - 1);
    const splitCount = splitVal * digitCount;
    endVal = beginVal + splitVal;
    end = begin + splitCount;
    while (n >= end) {
      beginVal = endVal;
      begin = end;
      endVal += splitVal;
      end += splitCount;
    }
  }
  return parseInt(String(beginVal)[n - begin], 10);
}

console.log(findNthDigit(3) === 3);
console.log(findNthDigit(11) === 0);
console.log(findNthDigit(111) === 0);
